#include <iostream>
#include <string>
#include <vector>
using namespace std;

/****
 * leecode_22 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 * 
 * 1 <= n <= 8
 * 解题思路：回溯(在解决问题时我们反复的寻找答案，一旦不满足条件我们就做回退操作，用来寻找所有的可能解，必须有终止条件)
 * 在这道题中我们可以看到答案是n对括号的不同组合，我们可以直观的看到一对括号由'(' , ')'组成 我们可以运用回溯这个思路
 * 即我们在定义的string res中反复放入左括号和右括号，在此过程中我们应先放入左括号，并且在最初定义dfs时我们就用l来代表
 * 放入左括号的数量，r则代表放入右括号的数量，然后再将我们要得到的答案放入 ans 中
 * 最重要的一点是我们应该在dfs函数最开始就应该判断好左括号的数量应该小于右括号的数量，这样才不会输出一些分不清的错误答案
 * 
 * 我们要知道回溯是用递归来实现操作的，可以简单想一想递归
 * 
 */

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string res;
        dfs(ans, res, n, n);
        return ans;
    }

    void dfs(vector<string> &ans, string &res, int l, int r) {
        if(l > r) {
            return;
        }

        if(l == 0 && r == 0) {
            ans.push_back(res);
            return;
        }

        if(l) { //试探左括号
            res.push_back('(');
            dfs(ans, res, l - 1, r);
            res.pop_back();//回退
        }

        if(r) { //试探右括号
            res.push_back(')');
            dfs(ans, res, l, r - 1);
            res.pop_back();//回退
        }
    }
};

// int main()
// {
//     int n;
//     cin >> n ;
//     Solution s1;
//     vector<string> ans = s1.generateParenthesis(n);
//     for(const string &s : ans) {
//         cout << s << "," ;
//     }
//     cout << endl;
//     return 0;
// }